package leetcode.code1191;

import java.math.BigInteger;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	class Int {
		public BigInteger value;

		public Int(long value) {
			this.value = BigInteger.valueOf(value);
		}

//		public Int max(BigInteger num) {
//			return value.compareTo(num) >= 0 ? this : new Int(num);
//		}

		public Int max(long num) {
			return value.compareTo(BigInteger.valueOf(num)) >= 0 ? this : new Int(num);
		}

		public Int max(Int num) {
			return value.compareTo(num.value) >= 0 ? new Int(value.longValue()) : new Int(num.value.longValue());//
		}

		public BigInteger mod(int mod) {
			return this.value.mod(BigInteger.valueOf(mod));
		}

		public Int add(Int num) {
			this.value = this.value.add(num.value);
			return new Int(this.value.longValue());
		}

		public Int add(int num) {
			this.value = this.value.add(BigInteger.valueOf(num));
			return new Int(this.value.longValue());
		}

		public Int sub(Int num) {
			this.value = this.value.subtract(num.value);
			return new Int(this.value.longValue());
		}

		public Int mul(int num) {
			this.value = this.value.multiply(BigInteger.valueOf(num));
			return new Int(this.value.longValue());
		}
	}

	int mod = (int) 1e9 + 7;

	public int kConcatenationMaxSum(int[] arr, int k) {
		Int[] max1 = this.max(arr, new Int(0), new Int(0), 0);
		if (k == 1) {// 这个wa的...
			return max1[0].mod(mod).intValue();
		}
		Int[] max2 = this.max(arr, max1[0], max1[1], arr[0]);
		// 增加一组最大值没有变大，那么增加多少个都无效
		if (max1[0] == max2[0] || k == 2) {// 就2个
			return max2[0].mod(mod).intValue();// 丢，这取max1[0]最后一个用例简直了
		}
		Int[] max3 = this.max(arr, max2[0], max2[1], arr[0]);
		// 两组就能产生最大，max2结束
		if (max2[0] == max3[0]) {
			return max2[0].mod(mod).intValue();
		}
		// 每增加一组都能扩大最大值
		return max3[0].sub(max2[0]).mul(k - 2).add(max2[0]).mod(mod).intValue();
//		return (int) ((max2[0] + (long) (max3[0] - max2[0]) * (k - 2)) % mod);// 这没mod，WA，没转long乘积 WA
	}

	// arr，前一个数组最大子数组，前一个数组以最后一位结尾的最大子数组，最大值基础
	public Int[] max(int[] arr, Int preMax, Int preMaxWithEnd, int basic) {
		Int last = new Int(preMaxWithEnd.add(arr[0]).value.intValue());
		last = last.max(basic);
		Int max = preMax.max(last);
		for (int i = 1; i < arr.length; i++) {
			Int cur = new Int(arr[i]);
			Int end = cur.max(last.add(cur));
			max = max.max(end);
			last = end;
		}
		return new Int[] { max, last };// 这个mod
	}

	@Override
	public void debug4() {
		System.out.println(9000030000L % mod);
//		System.out.println(1000000000 % mod);
//		System.out.println(1000000000 - 999999993);
		H.compare(1, this.kConcatenationMaxSum(H.str2array3("[1,-1]"), 1));
		H.compare(999999937, this.kConcatenationMaxSum(
				H.str2array3("[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]"), 100000));
		H.compare(4, this.kConcatenationMaxSum(H.str2array3("[4,-10,-2,-3,4]"), 1));
		H.compare(9, this.kConcatenationMaxSum(H.str2array3("[1,2]"), 3));
		H.compare(2, this.kConcatenationMaxSum(H.str2array3("[1,-2,1]"), 5));
		H.compare(0, this.kConcatenationMaxSum(H.str2array3("[-1,-2]"), 7));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
